//给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。 
//
// 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：head = [4,2,1,3]
//输出：[1,2,3,4]
// 
//
// 示例 2： 
//
// 
//输入：head = [-1,5,3,4,0]
//输出：[-1,0,3,4,5]
// 
//
// 示例 3： 
//
// 
//输入：head = []
//输出：[]
// 
//
// 
//
// 提示： 
//
// 
// 链表中节点的数目在范围 [0, 5 * 10⁴] 内 
// -10⁵ <= Node.val <= 10⁵ 
// 
//
// 
//
// 进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？ 
// Related Topics 链表 双指针 分治 排序 归并排序 👍 1666 👎 0

package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class SortList {
    public static void main(String[] args) {
        Solution solution = new SortList().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    class Solution {
        /*public ListNode sortList(ListNode head) {
            if (head == null) return null;
            ListNode cur = head;
            List<Integer> list = new ArrayList<>();
            while (cur != null) {
                list.add(cur.val);
                cur = cur.next;
            }

            Collections.sort(list);
            ListNode head1 = new ListNode(list.get(0));
            cur = head1;
            for (int i = 1; i < list.size(); i++) {
                cur.next = new ListNode(list.get(i));
                cur = cur.next;
            }

            return head1;
        }*/

        // 递归
        /*public ListNode sortList(ListNode head) {
            if (head == null && head.next == null) return head;

            // 前后指针找到中间节点
            ListNode slow = head, fast = head.next;
            while (fast.next != null && fast.next.next != null) {
                fast = fast.next.next;
                slow = slow.next;
            }

            // 递归将节点分开
            ListNode tmpNode = slow.next;
            // 注意设置为null,才是一个单链表
            slow.next = null;
            ListNode left = sortList(head);
            ListNode right = sortList(tmpNode);

            // 设置一个虚拟头节点，用来连接
            ListNode node = new ListNode(0);
            ListNode dummy = node;
            while (left != null && right != null) {
                if (left.val < right.val) {
                    node.next = left;
                    left = left.next;
                }else {
                    node.next = right;
                    right = right.next;
                }
                node = node.next;
            }

            // 合并还剩余的节点
            node.next = left == null ? right : left;

            // 返回头节点
            return dummy.next;
        }*/

        // 迭代
        public ListNode sortList(ListNode head) {
            if (head == null || head.next == null) return head;

            // 使用虚拟头节点,来记录
            ListNode dummy = new ListNode(0);
            dummy.next = head;
            int len = getLength(head);
            int itrv = 1;

            // 合并的区间等于链表长度就不在合并
            while (itrv < len) {
                // 表示当前节点
                ListNode h = dummy.next;
                ListNode pre = dummy;

                while (h != null) {
                    int i = itrv;
                    ListNode h1 = h;
                    for (; h != null && i > 0; i--) {
                        h = h.next;
                    }

                    // 如果没有第二条链表，直接break
                    if (i > 0) break;

                    i = itrv;
                    ListNode h2 = h;
                    // 如果有，找到第二条链表
                    for (; h != null && i > 0; i--) {
                        h = h.next;
                    }

                    // 此时开始合并2个链表

                    // 前部分链表的长度
                    int left = itrv;
                    // 后部分链表的长度，减i的情况就是如果后面链表长度不足itrv
                    int right = itrv - i;
                    while (left > 0 && right > 0) {
                        if (h1.val < h2.val) {
                            pre.next = h1;
                            h1 = h1.next;
                            left--;
                        } else {
                            pre.next = h2;
                            h2 = h2.next;
                            right--;
                        }
                        pre = pre.next;
                    }

                    // 连接剩余的
                    pre.next = left > 0 ? h1 : h2;

                    // 这对处理完，移动到最后，开始第二组，注意移动最长的
                    // 第二段可以不等于itrv
                    while (left > 0 || right > 0) {
                        pre = pre.next;
                        left--;
                        right--;
                    }

                    // 第二段头节点赋值给第一段
                    pre.next = h;
                }

                // 扩大两倍合并
                itrv *= 2;
            }

            return dummy.next;
        }

        public int getLength(ListNode head) {
            ListNode cur = head;
            int len = 0;
            while (cur != null) {
                cur = cur.next;
                len++;
            }
            return len;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}
